#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cmath>
using namespace std;
int st(int i)
{
    int find = 1;
    int ret = 1;
    int arr[1000] = { 0 };
    while (find == 1)
    {
        i = i % 1000 / 10;
        arr[ret++] = i * i;
        i = i * i;
        if (ret > 2)
        {
            for (int j = 1; j < ret-1; j++)
            {
                if (arr[j] == arr[ret - 1])
                {
                    find = 0;
                    break;
                }
            }
        }
    }
    return ret - 1;
}
int main()
{
    int n = 0;
    cin >> n;
    int arr[1000] = { 0 };
    int s[1000] = { 0 };
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    for (int i = 0; i < n; i++)
    {
        s[i] = st(arr[i]);
        cout << s[i] << endl;
    }
    return 0;
}